from typing import List


class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        if  len(pushed) != len(popped): return False

        stack = []
        i = 0
        for p in pushed:
            stack.append(p)
            while len(stack) and stack[-1] == popped[i]:
                stack.pop()
                i += 1
        return len(stack) == 0

if __name__ == '__main__':
    s = Solution().validateStackSequences([1,2,3,4,5], [4,5,3,2,1])
    
